package pro.softzhang.algo.lc600;

import pro.softzhang.algo.flag.theme.TIslands;
import pro.softzhang.algo.flag.x.XClassic;

import java.util.LinkedList;
import java.util.Queue;

/**
 *
 */
@XClassic
@TIslands
public class LC695_MaxAreaOfIsland {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public int maxAreaOfIsland(int[][] grid) {
            int width = grid.length, height = grid[0].length, maxArea = 0;
            boolean[][] visited = new boolean[width][height];
            for ( int i = 0; i < width; i++) {
                for (int j = 0; j < height; j++) {
                    if(grid[i][j] == 1 && !visited[i][j]) {
                        int area = calcArea(grid, visited, i, j);
                        maxArea = Math.max(maxArea, area);
                    }
                }
            }
            return maxArea;
        }

        private int calcArea(int[][] grid, boolean[][] visited, int i, int j) {
            Queue<int[]> q = new LinkedList<>();
            q.add(new int[]{i, j});
            visited[i][j] = true;
            int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            int area = 0;
            while (!q.isEmpty()) {
                int[] pos = q.remove();
                area++;
                for (int[] dir : dirs) {
                    int r = pos[0] + dir[0];
                    int c = pos[1] + dir[1];
                    if(r >= 0 && r < grid.length
                            && c >= 0 && c < grid[0].length
                            && grid[r][c] == 1 && !visited[r][c]) {
                        q.add(new int[]{r, c});
                        visited[r][c] = true;
                    }
                }
            }
            return area;
        }
    }

    /**
     * 沉岛思想
     */
    static
    class Solution1 {
        public int maxAreaOfIsland(int[][] grid) {
            int max = 0;
            for(int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    if (grid[i][j] == 1) {
                        max = Math.max(max, dfs(grid, i, j));
                    }
                }
            }
            return max;
        }

        /**
         * 深度优先搜索，递归实现
         * @return
         */
        private int dfs(int[][] grid, int i, int j) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == 0) {
                return 0;
            }

            // 关键 沉岛操作
            grid[i][j] = 0;

            int area = 1;
            area += dfs(grid, i, j + 1);
            area += dfs(grid, i, j - 1);
            area += dfs(grid, i + 1, j);
            area += dfs(grid, i - 1, j);
            return area;
        }
    }
}
